#include <stdio.h>


void heap(int *arr,int s,int p){
    int largest = p, l = p*2+1, r = p*2+2;

    if(l<s && arr[l]>arr[largest]){
        largest = l;
    }
    if(r<s && arr[r]>arr[largest]){
        largest = r;
    }

    if(largest!=p){
        int temp = arr[largest];
        arr[largest] = arr[p];
        arr[p] = temp;
        heap(arr,s,largest);  
    }

}

void heapSort(int *arr,int n){
    // 首先从最后一个非叶子节点开始堆化
    for(int i=n/2-1;i>-1;i--){
        heap(arr,n,i);
    }

    // 不断抽取堆顶值，并不断调整堆，直至排序完
    for(int s=n-1;s>0;s--){
        // 交换堆顶元素和最后一个元素
        int temp = arr[0];
        arr[0] = arr[s];
        arr[s] = temp;
        heap(arr,s,0);
    }
}

int main(){
    int arr[] = {218,224,391,443,22,337,1125,49,506};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr,n);
    
    for(int i=0;i<n;i++){printf("%d ",arr[i]);}
    return 0;
}